#include <vector>
using namespace std;
#include <iostream>

class Solution{
private:
    void qSortAndFindKthLeast(vector<int>& arr, int k, int l, int r){
        if(l >= r) return;
        int key = arr[(rand() % (r - l + 1)) + l];
        int i = l, left = l - 1, right = r + 1;
        while(i < right){
            if(arr[i] < key) std::swap(arr[++left], arr[i++]);
            else if(arr[i] == key) ++i;
            else std::swap(arr[--right], arr[i]);
        }
        //[l, left] [left + 1, right - 1] [right, r]
        int a = left - l + 1, b = right - l, c = r - l + 1;
        if(a > k) return qSortAndFindKthLeast(arr, k, l, left); //这里不下等号其实可以的！
        //因为a == k其实就已经找到了前k个了 else if那里一定是能返回的！
        else if(a + b >= k) return;
        else return qSortAndFindKthLeast(arr, k - a - b, right, r);
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k){
        srand((unsigned int)time(nullptr));
        qSortAndFindKthLeast(arr, k, 0, arr.size() - 1);
        return vector<int>(arr.begin(), arr. begin() + k);
    }
};


int main(){
    vector<int> v = {0,1,2,1,9,5,5,6,8,0,2,5,4,1};
    
    vector<int> ret =  Solution().getLeastNumbers(v, 10);
    for(auto x: ret) cout << x << " ";
    cout << endl;
    return 0;
}